package com.kevin.Code.Backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Vinlee Xiao
 * @Classname CombinationSumiii
 * @Description Leetcode 216 组合总和III 中等难度 回溯算法
 * @Date 2021/9/30 10:16
 * @Version 1.0
 */
public class CombinationSumiii {


    List<List<Integer>> result = new ArrayList<>();

    /**
     * @param k
     * @param n
     * @return
     */
    public List<List<Integer>> combinationSum3(int k, int n) {

        if (k > 9) {
            return null;
        }

        List<Integer> combine = new ArrayList<>();
        backtrack(combine, k, n, 1, 0);

        return result;
    }

    /**
     * @param combine
     * @param k
     * @param n
     * @param startIndex
     * @param preSum
     */
    public void backtrack(List<Integer> combine, int k, int n, int startIndex, int preSum) {


        //回溯结束的条件
        if (preSum == n && combine.size() == k) {

            result.add(new ArrayList<>(combine));
            return;
        }

        for (int i = startIndex; i <= 9; i++) {

            if (preSum < n) {
                combine.add(i);
                backtrack(combine, k, n, i + 1, preSum + i);
                combine.remove(combine.size() - 1);
            }
        }


    }

    public static void main(String[] args) {
        CombinationSumiii combinationSumiii = new CombinationSumiii();

        List<List<Integer>> lists = combinationSumiii.combinationSum3(3, 7);


        for (List<Integer> list : lists) {

            for (Integer e : list) {
                System.out.print(e + " ");
            }
            System.out.println();
        }
    }
}
